package ShortestPath;

import pojo.Edge;

import java.util.*;


/**
 * <p>
 * 玄学算法hhh，本来是不打算收录了，但毕竟也算半个《国产算法》还是支持一下叭
 * 注：本算法属于进阶算法数据结构课程并不设计，读者可选学，部分代码与之前的dijkstra雷同
 * 本算法其实作为最短路并不常用，更常用于判断负环（如差分约束中）
 * </p>
 * @author ：没天赋
 * @since 2025-2-28
 */
@SuppressWarnings(value = "all")
public class SPFA {
    //定义最大点数
    public static final int N = (int) (1e5 + 5);
    //定义边数组,这里*2是因为无向图
    public static Edge[] edges = new Edge[N << 1];
    //存邻接表头
    public static int[] head = new int[N];
    //存点到边的距离
    public static int[] dis = new int[N];
    //记录是否访问
    public static int[] vis = new int[N];
    //记录使用次数（判断负环的精髓）
    public static int[] used = new int[N];
    //点数n，边数m,下标id（记录边数）,入度u，出度v，权值w
    public static int n, m, id, u, v, w;
    public static Scanner sc = new Scanner(System.in);
    //定义队列（判负环时拿stack优化有奇效）
    public static Queue<Integer> queue = new LinkedList<>();

    //虽常用于判断负环，但大家一是学习最短路二是不打算法竞赛遇不到判负环，所以这里仍然展示最短路
    public static void main(String[] args) {
        n = sin();
        m = sin();
        for (int i = 0; i < m; i++) {
            u = sin();
            v = sin();
            w = sin();
            //无向图所以双边都要建立（这就是为什么边数组要开双倍N<<1）
            add(u, v, w);
            add(v, u, w);
        }
        System.out.println(spfa());
    }

    public static int spfa() {
        //初始化1到各点的距离为最大值
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[1] = 0;
        vis[1] = 1;
        queue.add(1);
        while (!queue.isEmpty()) {
            Integer temp = queue.poll();
            //出队列一次遍历次数+1
            used[temp]++;
            //遍历完之后，出队列的点就出队列了，所以要重新赋值
            vis[temp] = 0;

            //如果使用次数>节点数证明存在负环
            if (used[temp] > n) {
                return -1;
            }

            //遍历并松弛临边
            for (int i = head[temp]; i != 0; i = edges[i].next) {
                int x = edges[i].to;
                if (dis[x] > dis[temp] + edges[i].val) {
                    dis[x] = dis[temp] + edges[i].val;
                    if (vis[x] == 0) {
                        //添加进队列
                        vis[x] = 1;
                        queue.add(x);
                    }
                }
            }
        }
        return dis[n];
    }

    /**
     * 增边
     *
     * @param x
     * @param y
     * @param z
     */
    public static void add(int x, int y, int z) {
        id++;
        edges[id] = new Edge(y, head[x], z);
        head[x] = id;
    }

    /**
     * 读取整数方法
     *
     * @return
     */
    public static int sin() {
        return sc.nextInt();
    }
}

//测试数据同dijkstra